'''
差分数组:
    add(l, r, v), [l, r] 都加 v
    get_arr(): 返回整体数组
add: O(1)
查询: O(N)
'''
import random


class DifferenceArray:
    def __init__(self, size):
        self.info = [0] * (size + 1)    # 防止右边界越界，也可在逻辑中判断
        self.size = size

    def add(self, l, r, v):
        self.info[l] += v
        self.info[r + 1] -= v

    def get_arr(self):
        nums = [0] * self.size
        nums[0] = self.info[0]
        for i in range(1, self.size):
            nums[i] = nums[i - 1] + self.info[i]
        return nums

class Compare:
    def __init__(self, size):
        self.info = [0] * size

    def add(self, l, r, v):
        for i in range(l, r + 1):
            self.info[i] += v

    def get_arr(self):
        return self.info

def a():
    c1 = Compare(10)
    c1.add(1, 3, 4)
    c1.add(2, 5, 4)
    c1.add(3, 7, 4)
    c1.add(0, 5, 4)
    c1.add(7, 9, 4)
    c1.add(9, 9, 4)
    c2 = DifferenceArray(10)
    c2.add(1, 3, 4)
    c2.add(2, 5, 4)
    c2.add(3, 7, 4)
    c2.add(0, 5, 4)
    c2.add(7, 9, 4)
    c2.add(9, 9, 4)
    arr1 = c1.get_arr()
    arr2 = c2.get_arr()
    print(arr1)
    print(arr2)
    print(arr1 == arr2)

def test(n_test, n_maximum_size, n_maximum_operation):
    for _ in range(n_test):
        size = random.randint(1, n_maximum_size)
        c1 = DifferenceArray(size)
        c2 = Compare(size)
        m = random.randint(1, n_maximum_operation)
        ops = []
        for _ in range(m):
            l = random.randint(0, size - 1)
            r = random.randint(l, size - 1)
            v = random.randint(0, 10)
            c1.add(l, r, v)
            c2.add(l, r, v)
            ops.append((l, r, v))
        arr1 = c1.get_arr()
        arr2 = c2.get_arr()
        if arr1 != arr2:
            print('操作：', ops)
            print(arr1)
            print(arr2)
            print("error!")
            break


if __name__ == '__main__':
    print("请输入测试轮数: ", end='')
    time = int(input())
    print("请输入最大数组最大size: ", end='')
    maximum_size = int(input())
    print("请输入单次测试最大操作次数: ", end='')
    maximum_operation_time = int(input())
    test(time, maximum_size, maximum_operation_time)
    print('测试结束!')

